// 给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

// 假定 BST 有如下定义：
// 结点左子树中所含结点的值小于等于当前结点的值
// 结点右子树中所含结点的值大于等于当前结点的值
// 左子树和右子树都是二叉搜索树



// 暴露接口
function findMode(root: TreeNode | null): number[] {
    const hashMap = new Map<number, number>();
    const res: number[] = [];// 结果数组
    findMode_DFS(root, hashMap);// 中序遍历
    let maxCount = 0;
    // 找最大个数
    for(let value of hashMap.values()){
        maxCount = Math.max(maxCount,value);
    }
    // 找匹配结果加入结果数组
    for(let [key,value] of hashMap.entries()){
        if(value === maxCount) res.push(key);
    }
    return res;
};
// 深度优先辅助方法
function findMode_DFS(root: TreeNode | null, hashMap: Map<number, number>) {
    // 递归出口
    if (root === null) {
        return;
    }
    let curr: number = root.val;
    // 更新哈希表信息
    if (hashMap.has(curr)) {
        hashMap.set(curr, hashMap.get(curr)! + 1);
    } else {
        hashMap.set(curr, 1);
    }
    // 中序遍历--->中、左、右
    findMode_DFS(root.left, hashMap);
    findMode_DFS(root.right, hashMap);
}


// 这道题的难度总体上来说也是比较小的
// 比较容易想到的解法是使用中序遍历走一遍整棵树
// 边走树一遍更新维护的哈希表，我们使用哈希表来记录节点值和对应的的出现个数
// 走完树后，我们对哈希表进行两轮循环
// 第一轮循环主要是找最大的value值并记录
// 第二轮循环主要是找与第一轮记录的最大value值相等的key值并加入结果数组中
// 返回结果数组即可得到这道题目的答案
// 但本题也存在哈希表记录数据的空间冗余，故存在使用莫里斯遍历的更好解法，在此不再展开